19. 找单词

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const lines = [];
let n;
rl.on('line', (line) => {
    lines.push(line);
    if (lines.length === 1) {
        n =parseInt(lines[0]);
    }
    if (n && lines.length === n+2) {
        lines.shift();
        const str = lines.pop();
        const grid = lines.map((line) => line.split(','));
        console.log(find(grid, n, str));
        lines.length = 0;
    }
});

function find(grid, n, tar) {
    const visited = Array.from(Array(n), () => Array(n).fill(false));
    const path = [];
    for(let i=0; i<n; i++) {
        for(let j=0; j<n; j++) {
            if (grid[i][j] === tar[0]) {
                const found = dfs(i, j, 0, path);
                if (found) {
                    let res = '';
                    for(const pos of path) {
                        res += pos[0] + ',' + pos[1] + ',';
                    }
                    res = res.slice(0, -1);
                    return res;
                }
            }
        }
    }
    return 'N';
}

function dfs(i, j, k, path) {
    if (i<0 || i>=n || j<0 || j>=n || visited[i][j] || tar[k] !== grid[i][j]) {
        return false;
    }
    path.push([i,j]);
    visited[i][j] = true;
    if (k === tar.length - 1) {
        return true;
    }
    const dir = [[0,1],[0,-1],[1,0],[-1,0]];
    for(const d of dir) {
        const ni = i + d[0];
        const nj = j + d[1];
        const res = dfs(ni, nj, k+1, path);
        if (res) {
            return true;
        }
    }
    visited[i][j] = false;
    path.pop();
    return false;
}